Сортировки, куча, бинпоиск

A. Простая сортировка

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 64 мегабайта

В этой задаче вам нужно реализовать любую из пройденных сортировок, работающих за время $O(n \log n)$. Использовать встроенные в язык сортировки и структуры данных запрещается.

Дан массив целых чисел. Ваша задача — отсортировать его в порядке неубывания.

Входные данные

В первой строке содержится число $n$ $(1 ⩽ n ⩽ 100\ 000)$ — количество элементов в массиве. Во второй строке находятся $n$ целых чисел, по модулю не превосходящих $10^9$.

Выходные данные

Выведите этот же массив в порядке неубывания.

Пример

Входные данные

10
1 8 2 1 4 7 3 2 3 6

Выходные данные

1 1 2 2 3 3 4 6 7 8

Решение

B. Сортировка подсчетом

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 64 мегабайта

А в этой задаче вам нужно реализовать сортировку подсчетом. Использовать другие сортировки запрещается.

Дан массив из $n$ элементов, которые принимают целые значения от 0 до 100. Отсортируйте этот массив в порядке неубывания элементов.

Входные данные

В первой строке содержится число $n$ $(1 ⩽ n ⩽ 200\ 000)$ — количество элементов в массиве. Во второй строке находятся n целых чисел, от 0 до 100 каждое.

Выходные данные

Выведите отсортированный массив.

Пример

Входные данные

5
7 3 4 2 5

Выходные данные

2 3 4 5 7

Решение

C. Количество инверсий

Ограничение по времени на тест: 5 секунд

Ограничение по памяти на тест: 256 мегабайт

Напишите программу, которая для заданного массива $A = ⟨a_1, a_2, …, a_n⟩$ находит количество пар $(i, j)$ таких, что $i < j$ и $a_i > a_j$.

Входные данные

Первая строка входного файла содержит натуральное число $n$ $(1 ⩽ n ⩽ 500\ 000)$ — количество элементов массива. Вторая строка содержит $n$ попарно различных элементов массива $A$ $(0 ⩽ a_i ⩽ 10^6)$.

Выходные данные

В выходной файл выведите одно число — ответ на задачу.

Пример

Входные данные

4
1 2 4 5

Выходные данные

0

Входные данные

4
5 4 2 1

Выходные данные

6

Решение

D. Хипуй!

Ограничение по времени на тест: 3 секунды

Ограничение по памяти на тест: 256 мегабайт

В этой задаче вам необходимо организовать структуру данных Heap для хранения целых чисел, над которой определены следующие операции:

• Insert(X) — добавить в Heap число $X$;
• Extract — достать из Heap наибольшее число (удалив его при этом).

Эту задачу нужно решить без использования встроенных структур данных для поиска максимального числа.

Входные данные

Во входном файле записано количество команд $n$ $(1 ⩽ n ⩽ 100\ 000)$, потом последовательность из $n$ команд, каждая в своей строке.

Каждая команда имеет такой формат: 0 <число> или 1, что означает соответственно операции Insert(<число>) и Extract. Добавляемые числа находятся в интервале от $1$ до $10^7$ включительно.

Гарантируется, что при выполнении команды Extract в структуре находится по крайней мере один элемент.

Выходные данные

В выходной файл для каждой команды извлечения необходимо вывести число, полученное при выполнении команды Extract.

Пример

Входные данные

7
0 100
0 10
1
0 5
0 30
0 50
1

Выходные данные

100
50

Решение

E. Быстрый поиск в массиве

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 512 мегабайт

Дан массив из $n$ целых чисел. Все числа от $−10^9$ до $10^9$.

Нужно уметь отвечать на запросы вида «Cколько чисел имеют значения от $l$ до $r$»?

Входные данные

Число $n$ $(1 ⩽ n ⩽ 10^5$). Далее $n$ целых чисел.

Затем число запросов $k$ $(1 ⩽ k ⩽ 10^5)$.

Далее $k$ пар чисел $l, r$ $(−10^9 ⩽ l ⩽ r ⩽ 10^9)$ — собственно запросы.

Выходные данные

Выведите $k$ чисел — ответы на запросы.

Пример

Входные данные

5
10 1 10 3 4
4
1 10
2 9
3 4
2 2

Выходные данные

5 2 2 0

Решение

F. Приближенный двоичный поиск

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Даны два массива. Первый массив отсортирован по неубыванию, второй массив содержит запросы — целые числа.

Для каждого запроса выведите число из первого массива наиболее близкое (то есть с минимальным модулем разности) к числу в этом запросе. Если таких несколько, выведите меньшее из них.

Входные данные

В первой строке входных данных содержатся числа $n$ и $k$ $(0 < n, k ⩽ 10^5)$. Во второй строке задаются $n$ чисел первого массива, отсортированного по неубыванию, а в третьей строке — $k$ чисел второго массива. Каждое число в обоих массивах по модулю не превосходит $2 \cdot 10^9$.

Выходные данные

Для каждого из $k$ чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.

Пример

Входные данные

5 5
1 3 5 7 9
2 4 8 1 6

Выходные данные

1
3
7
1
5

Решение

G. Очень Легкая Задача

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще $n$ копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за $x$ секунд, а другой — за $y$. (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.

Входные данные

На вход программы поступают три натуральных числа $n$, $x$ и $y$, разделенные пробелом $(1 ⩽ n ⩽ 2 \cdot 10^8, 1 ⩽ x, y ⩽ 10)$.

Выходные данные

Выведите одно число — минимальное время в секундах, необходимое для получения $n$ копий.

Пример

Входные данные

4 1 1

Выходные данные

3

Входные данные

5 1 2

Выходные данные

4

Решение

H. Квадратный корень и квадратный квадрат

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Найдите такое число $x$, что $x^2 + \sqrt{x}$, с точностью не менее 6 знаков после точки.

Входные данные

В единственной строке содержится вещественное число $1.0 ⩽ C ⩽ 10^{10}$.

Выходные данные

Выведите одно число — искомый $x$.

Пример

Входные данные

2.0000000000

Выходные данные

1.0

Входные данные

18.0000000000

Выходные данные

4.0

Решение

I. Поляна дров

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Маленький мальчик Ферма́ живет в деревне. Наступают холодные времена, поэтому бабушка попросила мальчика сходить в лес, чтобы собрать дров. В лесу около деревни, в которой живет Ферма, находится волшебная Поляна Дров, на которой всегда лежат дрова, и никогда не кончаются. Естественно, Ферма должен пойти именно туда.

Единственная проблема заключается в том, что идти до Поляны не очень близко, тем более что скорость передвижения по лесу намного меньше, чем скорость передвижения по полю, в котором находится деревня.

• Деревня находится в точке с координатами $(0, 1)$.
• Поляна находится в точке с координатами $(1, 0)$.
• Граница между лесом и полем — горизонтальная прямая $y = a$, где $a$ — некоторое число $(0 ⩽ a ⩽ 1)$.
• Скорость передвижения по полю составляет $V_p$, скорость передвижения по лесу — $V_f$. Вдоль границы можно двигаться как по лесу, так и по полю.

Найдите точку, в которой мальчик Ферма должен войти в лес, чтобы дойти до Поляны Дров как можно быстрее.

Входные данные

В первой строке входного файла содержатся два положительных целых числа — $V_p$ и $V_f$ $(1 ⩽ V_p, V_f ⩽ 10^5)$. Во второй строке содержится единственное вещественное число — координата по оси $O_y$ границы между лесом и полем $a$ $(0 ⩽ a ⩽ 1)$

Выходные данные

В единственной строке выходного файла выведите вещественное число с точностью не менее 4 знаков после запятой — координата по оси $O_x$ точки, в которой мальчик Ферма должен войти в лес.

Пример

Входные данные

5 3
0.4

Выходные данные

0.783310604

Решение

J. K-best

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

У Демьяны есть $n$ драгоценностей. Каждая из драгоценностей имеет ценность $v_i$ и вес $w_i$. С тех пор, как её мужа Джонни уволили в связи с последним финансовым кризисом, Демьяна решила продать несколько драгоценностей. Для себя она решила оставить лишь $k$ лучших. Лучших в смысле максимизации достаточно специфического выражения: пусть она оставила для себя драгоценности номер $i_1, i_2, …, i_k$, тогда максимальной должна быть величина

$$\frac{\sum\limits_{j=1}^{k}v_{i_j}}{\sum\limits_{j=1}^{k}w_{i_j}}$$

Помогите Демьяне выбрать $k$ драгоценностей требуемым образом.

Входные данные

На первой строке $n$ и $k$ $(1 ⩽ k ⩽ n ⩽ 100\ 000)$.

Следующие $n$ строк содержат пары целых чисел $v_i$, $w_i$ $(0 ⩽ v_i ⩽ 10^6,$ $1 ⩽ w_i ⩽ 10^6)$, сумма всех $v_i$ не превосходит $10^7$, сумма всех $w_i$ также не превосходит $10^7)$.

Выходные данные

Выведите $k$ различных чисел от $1$ до $n$ — номера драгоценностей. Драгоценности нумеруются в том порядке, в котором перечислены во входных данных. Если есть несколько оптимальных ответов, выведите любой.

Пример

Входные данные

3 2
1 1
1 2
1 3

Выходные данные

1
2

Решение

K. Разделение массива

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 256 мегабайт

Дан массив из $n$ положительных целых чисел. Нужно разбить его на $k$ отрезков так, чтобы максимальная сумма на отрезке была минимально возможной.

Входные данные

Первая строка содержит целые числа $n$ и $k$ $(1 ⩽ k ⩽ n ⩽ 10^5)$. Вторая строка содержит элементы массива $a_i$ $(1 ⩽ a_i ⩽ 10^9)$.

Выходные данные

Выведите одно число — минимально возможную максимальную сумму на отрезке.

Пример

Входные данные

10 4
1 3 2 4 10 8 4 2 5 3

Выходные данные

12

Решение

L. Таблица умножения

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 256 мегабайт

Петя составил таблицу умножения размера $n \times n$. Ячейка в $i$-й строке и $j$-м столбце содержит значение $i \cdot j$. Петю заинтересовал вопрос: какое число в таблице является $k$-м по возрастанию? Помогите Пете ответить на этот вопрос.

Входные данные

Ввод содержит два целых числа $n$ и $k$ $(1 ⩽ n ⩽ 10^5, 1 ⩽ k ⩽ n^2)$.

Выходные данные

Выведите одно число — $k$-е число по возрастанию в таблице.

Пример

Входные данные

3 4

Выходные данные

3

Входные данные

5 16

Выходные данные

10

Решение

M. K-я сумма

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 256 мегабайт

Есть два массива $a$ и $b$, каждый из которых состоит из $n$ чисел. Для каждой пары чисел $(i, j): 1 ⩽ i, j ⩽ n$ выпишем сумму чисел $a_i + b_j$. Найдите в полученном множестве сумм $k$-ю по возрастанию.

Входные данные

Первая строка содержит целые числа $n$ и $k$ $(1 ⩽ n ⩽ 10^5, 1 ⩽ k ⩽ n^2)$. Вторая строка содержит элементы массива $a$, третья строка содержит элементы массива $b$. Все элементы массивов — целые положительные числа, не больше $10^9$.

Выходные данные

Выведите одно число — искомая $k$-я сумма.

Пример

Входные данные

5 10
4 2 6 4 8
7 3 1 9 5

Выходные данные

9

Решение